package basic_practice_1006;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		List<Integer>  Fibonacci=new ArrayList<>();

		Fibonacci.add(1);
		Fibonacci.add(2);
		Fibonacci.add(3);
		Fibonacci.add(5);
		Fibonacci.add(8);
		Fibonacci.add(13);

		Scanner scanner=new Scanner(System.in);
		
		while(scanner.hasNext()) {
			
			int n=scanner.nextInt();
			int[]X=new int[n];
			
			for(int i=0;i<n;i++) {
				X[i]=scanner.nextInt();
				
				while(X[i]>=Fibonacci.size()) {
					int fib=Fibonacci.get(Fibonacci.size()-2)+Fibonacci.get(Fibonacci.size()-1);
					
					fib=fib%10000;
					Fibonacci.add(fib);
				}
				String out=""+Fibonacci.get(X[i]-1);
				while(out.length()<4) {
					out="0"+out;
				}
				
				System.out.print(out);
			}
			System.out.println();
			
			
		}
		scanner.close();
	}
}
